package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * 1110. 删点成林
 * @author feizns
 * @since 2020/3/17
 */
public class DelNodes {

    public static void main(String[] args) {

    }

    List<TreeNode> ans = new LinkedList<>();

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> set = new HashSet<>();
        for (int i : to_delete)
            set.add(i);
        dfs(root, set, true);
        return ans;
    }

    private TreeNode dfs(TreeNode root, Set<Integer> removes, boolean parentDeleted) {
        if ( root != null ) {
            boolean curtDeleted = removes.contains(root.val);
            if ( parentDeleted && !curtDeleted )
                ans.add(root);
            root.left = dfs(root.left, removes, curtDeleted);
            root.right = dfs(root.right, removes, curtDeleted);
            return curtDeleted ? null : root;
        }
        return null;
    }

}
